Mechanism design

There are $N$$N$ expected utility maxmizes player who must jointly decide among a set $X$$X$ of possible outcomes.

Each player $i$$i$ has privately observed type ${\theta }_i$$\theta_i$ drawn from a set ${\mathrm{\Theta }}_i$$\Theta_i$ according to commonly known probability distribution. That is the distribution of player's type is common knowledge, but the realized tyype is only known by the player.

A player's type ${\mathrm{\Theta }}_i$$\Theta_i$ represents her preference over the outcomes in $X,x\in X$$X, x\in X$.

A mechanism $(s,f)$$(s,f)$ is a set of strategy sets $S=S_1\times \cdots \times S_N$$S = S_1\times \dots \times S_N$ for each player , plus a rule $f:S\to X$$f: S\rightarrow X$ mapping from player's strategies to an outcome.

We can think of $S_i$$S_i$ as the set of possible messages that player $i$$i$ can send to some control computer, and the function $f$$f$ describes the way the computer translates messages into an outcome.

A direct mechanism is one in which $S_i={\mathrm{\Theta }}_i$$S_i = \Theta_i$ for each player $i$$i$ that is under a direct mechanism players are asked to report their types.

Example

There are $N$$N$ farmers who are thinking about building a road into town which costs $\mathrm{\$}C$$\$C$ . Farmer $i$$i$ would drive utility $u_i$$u_i$ if the road is built. Farmers know their own utility but not others.

Building this road is socially efficient if $\sum _{i\in \mathbb{N}}{u}_i\ge C$$\sum_{i\in \N} u_i \geq C$.

We will introduce a mechanism with the following properies

$$\begin{array}{}\text{(1)}& v_i=u_i-\frac{C}{N}\end{array}$$

This is $i$$i$'s valuation,

• (A) The road is built if and only if $\sum v_i\ge 0$$\sum v_i \geq 0$

• (B) Reporting $v_i$$v_i$ truthfully is a best response for each farmer $i$$i$ to any strategies by the other farmers.

• (C) The mechanism does not require any outside funds.

This mechanism is called Vickreg-Groues-Clarke (VCG) mechanism $\to$$\rightarrow$​ pivot mechanism

Let $\hat{v}$$\hat v$ be framer $i$$i$'s reported valuation, and let ${\hat{v}}_{-i}$$\hat v_{-i}$ be the vector of anyone else's reported valuation. The vector $\hat{v}=({\hat{v}}_i,{\hat{v}}_{-i})$$\hat v= (\hat v_i, \hat v_{-i})$ includes everyone's reports.

The mechanism specifies two things as a fucntion of reported valuations.

First function specifies whether the road $i$$i$'s built or not

$$\begin{array}{}\text{(2)}& D(\hat{v})=1\text{ represents the road is built, = 0 o.w.}\end{array}$$

Second is tax function,

$t_i(\hat{v})$$t_i(\hat v)$ is taxes paid by farmer $i$$i$ , it could be negative and it is paid regardless of whether or not the road is built. That is, farmer $i$$i$ pays $t_i(\hat{v})+D(\hat{v})\frac{C}{N}$$t_i(\hat v) + D(\hat v) \frac{C}{N}$

$$\begin{array}{}\text{(3)}& \begin{array}{rl}D(\hat{v})& =1\text{ if }\sum _i{\hat{v}}_i\ge 0\\ D(\hat{v})& =0\text{ o.w.}\end{array}\end{array}$$

And the tax function,

$$\begin{array}{}\text{(4)}& \begin{array}{rl}{t}_i(\hat{v})& =0\text{ if }\sum _k{\hat{v}}_k\ge 0\text{ and }\sum _{k\ne i}{\hat{v}}_k\ge 0\\ t_i(\hat{v})& =0\text{ if }\sum _k{\hat{v}}_k<0\text{ and }\sum _{k\ne i}{\hat{v}}_k<0\end{array}\end{array}$$

The above two formula represents that if you are not the pivot guy, then the tax for you is 0.

$$\begin{array}{}\text{(5)}& \begin{array}{rl}{t}_i(\hat{v})& =\sum _{k\ne i}{\hat{v}}_k\text{ if }\sum _k{\hat{v}}_k<0\text{ and }\sum _{k\ne i}{\hat{v}}_k\ge 0\\ t_i(\hat{v})& =-\sum _{k\ne i}{\hat{v}}_k\text{ if }\sum _k{\hat{v}}_k\ge 0\text{ and }\sum _{k\ne i}{\hat{v}}_k<0\end{array}\end{array}$$

Farmer $i$$i$​ pays a tax only if his valuation is pivotal. The outcome of the tax is equal to the externality that he creats.

Next, we check whether VCG mechanism satisfies propertoes A,B,C

• We wanna check For A first,

  Decision rule $D(\hat{v})$$D(\hat v)$​​ is defined so that if farmers report their true valuation the road is built exactly when it is socially efficient. So as long as farmers tell the truth, property A is satisfied.

  So if property B satisfies (telling the truth is the best response for everyone, then A automatically satsified)

Then the question becomes: DO FARMERS TELL TRUTH?

We need to check that reporting $\hat{v}=v_i$$\hat v = v_i$ is always the best response.

We have four cases

• $\sum _{k\ne i}{\hat{v}}_k\ge 0$$\sum_{k\neq i } \hat v_k \geq 0$ and $v_i\ge -\sum _{k\ne i}{\hat{v}}_k$$v_i \geq - \sum_{k\neq i} \hat v_k$. (This is corresponding to the first row in tax function)

  If $i$$i$ reports the truth, he gets payoff $v_i$$v_i$ and the road is built. He pays no addition taxes.

  If he deviates to higher value (he reports ${\hat{v}}_i>-\sum _{k\ne i}{\hat{v}}_k$$\hat v_i > - \sum_{k\neq i} \hat v_k$​), no changes, because the road is still built and no externality generates.

  If he deviates to some lower value (say he reports ${\hat{v}}_i<-\sum _{k\ne i}{\hat{v}}_k$$\hat v_i < -\sum_{k\neq i} \hat v_k$), then the road is not built, so he has to pay the externality that is $t_i(\hat{v})=\sum _{k\ne i}{\hat{v}}_k$$t_i(\hat v) = \sum_{k\neq i} \hat v_k$. The payoff for him is $-t_i(\hat{v})=-\sum _{k\ne i}{\hat{v}}_k$$-t_i(\hat v) = - \sum_{k\neq i} \hat v_k$. However, we know that $v_i\ge -\sum _{k\ne i}{\hat{v}}_k$$v_i \geq - \sum_{k\neq i} \hat v_k$, then he has no incentive to deviate.

• $\sum _{k\ne i}{\hat{v}}_k\ge 0$$\sum_{k\neq i } \hat v_k \geq 0$ and $v_i<-\sum _{k\ne i}{\hat{v}}_k$$v_i < - \sum_{k\neq i} \hat v_k$,

  IF $i$$i$ reports the truth $v_i$$v_i$, then he gets payoff $-\sum _{k\ne i}{\hat{v}}_k$$-\sum_{k\neq i} \hat v_k$.

  If he deviates to any lower value, nothing change, same payoff.

  If he divates to some higher value, say ${\hat{v}}_i\ge -\sum _{k\ne i}{\hat{v}}_k$$\hat v_i \geq - \sum_{k\neq i} \hat v_k$, then the road is built, and he is no longer the pivot, the payoff for him is $v_i<-\sum _{k\ne i}{\hat{v}}_k$$v_i < - \sum_{k\neq i} \hat v_k$ , even worse!

  Then he has no incentive to deviate.

Homework

show that $v_i$$v_i$ is BR in the other two cases.

• $\sum _{k\ne i}{\hat{v}}_k<0$$\sum_{k\neq i} \hat v_k < 0$ and $v_i<-\sum _{k\ne i}{\hat{v}}_k$$v_i< -\sum_{k\neq i} \hat v_k$​

  If farmer $i$$i$ reports the truth $v_i$$v_i$, then the road is not built, he gets payoff $0$$0$,

  If he deviates to any lower payoff, the road is still not built, then there is no change on payoffs.

  If he deviates to some higher payoff, ${\hat{v}}_i\ge -\sum _{i\ne k}{\hat{v}}_k$$\hat v_i \geq - \sum_{i \neq k} \hat v_k$, then the road is built, and trigger one tax of $-\sum _{i\ne k}{v}_k$$-\sum_{i\neq k} v_k$ . The payoffs he receives is then $v_i-\sum _{k\ne i}{\hat{v}}_k<0$$v_i -\sum_{k\neq i} \hat v_k<0$. So in this case, farmer $i$$i$ does not have any incentive to deviate.

• $\sum _{k\ne i}{\hat{v}}_k<0$$\sum_{k\neq i} \hat v_k < 0$ and $v_i\ge -\sum _{k\ne i}{\hat{v}}_k$$v_i \geq -\sum_{k\neq i} \hat v_k$​

  If farmer $i$$i$ reports the truth, then the road is built, so he gets the payoff of $v_i-\sum _{k\ne i}{\hat{v}}_k>0$$v_i - \sum_{k\neq i} \hat v_k >0$

  If he reports higher price, road is still built and no change in payoffs.

  If he reporst some lower price, then $v_i<-\sum _{k\ne i}{\hat{v}}_k$$v_i < -\sum_{k\neq i} \hat v_k$, the road is not built, then his payoff becomes 0. So report truth is still the best response and he does not have any incentives to deviate.

In any of the four cases, telling truth is BR to any possible reported valuation of others. So property B is satisfied and consequently property A is satisfied.

For property C, it is also satisfied bcecause whenever the road is built, it collects $\frac{C}{N}$$\frac CN$ from each farmer,l and any additional collected tax is positive. Thus the mechanism either breaks even or runs surplus.

Homework

What do we do with surplus? Explain.

We only have surplus under two cases.